package com.yusong.algorithm.kmp;


/**
 * KMP String Search Test
 * https://www.zhihu.com/question/21923021/answer/37475572
 */
public class KMPTest {




    /**
     * 构造 pattern 的最大匹配数表
     * @param pattern
     * @return
     */
    private static int[] calculateMaxMatchLengths(String pattern) {
        int[] maxMatchLengths = new int[pattern.length()];
        int maxLength = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (maxLength > 0 && pattern.charAt(maxLength) != pattern.charAt(i)) {
                maxLength = maxMatchLengths[maxLength - 1]; // ①
            }
            if (pattern.charAt(i) == pattern.charAt(maxLength)) {
                maxLength++; // ②
            }
            maxMatchLengths[i] = maxLength;
        }
        return maxMatchLengths;
    }


    public static void main(String[] args){
        String pattern = "abababzababab";
        System.out.println(calculateMaxMatchLengths(pattern));


    }
}
